/*
 * dbl_list.c
 *
 *  Created on: 04/06/2012
 *      Author: Roy
 */



#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <stdio.h>
#include "dbl_list.h"
//********************************************** Generic List*************************************

//--help functions--//
//create node with given next previous address
static Node createNode(Node next, Node previous,List list,ListElement data){
	Node returnNode = (Node) malloc(sizeof(*returnNode));
	if (!returnNode){
		return NULL;
	}
	returnNode->next = next;
	returnNode->previous = previous;
	if(!list){
		returnNode->data = NULL;
	}
	else{
		returnNode->data = list->copy(data);
	}
	return returnNode;
}

//get the data in the node.
static ListElement getNodeElement(Node node){
	if(!node){
		return NULL;
	}
	return node->data;
}

//get the next node.
static ListElement getNextNode(Node node){
	if(!node){
		return NULL;
	}
	return node->next;
}


//since we get and set allot theese addresses, it's much easier to understand
//when dony by functions:

//get the list current adrees (point to node.)
static Node getListCurrentAddress(List list){
	if(!list){
		return NULL;
	}
	return list->current;
}

// set the current field in list to a given Node Address
// if list is NULL, then dont do anything(!);
static void setListCurrentAddress(List list,Node address){
	if(!list){
		return;
	}
	list->current = address;
	return;
}

//set the head address of a list
// if list is NULL, return NULL
static Node getListHeadAddress(List list){
	if(!list){
		return NULL;
	}
	return list->head;
}
//-----//


List listCreate(CopyListElement copyElement, FreeListElement freeElement){
	if(!copyElement || !freeElement){
		return NULL;
	};
	List returnList = (List) malloc(sizeof(struct List_t));
	if(!returnList){
		return NULL;
	}
	returnList->copy = copyElement;
	returnList->freeElement = freeElement;
	Node dummyTailNode = createNode(NULL,NULL,NULL,NULL);
	returnList->head = dummyTailNode;
	returnList->tail = dummyTailNode;
	returnList->listSize = 0;
	setListCurrentAddress(returnList,NULL);
	if(!returnList->head){
		listDestroy(returnList);
		return NULL;
	}
	return returnList;
}


List listCopy(List list){
	int i;
	if(!list){
		return NULL;
	}
	List returnList = listCreate(list->copy,list->freeElement);
	if(!returnList){
		return NULL;
	}
	Node oldListCurrentNode = getListCurrentAddress(list);
	ListElement copyData = listGetFirst(list);
	for (i = 0; i < list->listSize; ++i) {
		listInsertLast(returnList,copyData);
		if(oldListCurrentNode==getListCurrentAddress(list)){
			setListCurrentAddress(returnList,returnList->tail->previous);
		}
		copyData = listGetNext(list);
	}
	list->current = oldListCurrentNode;
	return returnList;
}


int listGetSize(List list){
	if(!list){
		return -1;
	}
	return list->listSize;
}


ListElement listGetFirst(List list){
	if(!list || (listGetSize(list)==0)){
		return NULL;
	}
	setListCurrentAddress(list,getListHeadAddress(list));
	return getNodeElement(getListCurrentAddress(list));
}


ListElement listGetNext(List list){
	if(!list || list->tail==getListHeadAddress(list) || !(list->current)){
		return NULL;
	}
	Node nextListNode = getNextNode(getListCurrentAddress(list));
	if(nextListNode==list->tail){
		list->current=NULL;
		return NULL;
	}
	list->current = nextListNode;
	return getNodeElement(nextListNode);
}


ListElement listGetCurrent(List list){
	if(!list || !getListCurrentAddress(list)){
		return NULL;
	}
	return(getNodeElement(getListCurrentAddress(list)));
}

ListResult listInsertFirst(List list, ListElement element){
	if(!list){
		return LIST_NULL_ARGUMENT;
	}
	Node nextNode = getListHeadAddress(list);
	Node insertNode = createNode(nextNode,NULL,list,element);
	if(!insertNode){
		return LIST_OUT_OF_MEMORY;
	}
	nextNode->previous=insertNode;
	list->head = insertNode;
	list->listSize++;
	return LIST_SUCCESS;
}

ListResult listInsertLast(List list, ListElement element){
	if(!list){
		return LIST_NULL_ARGUMENT;
	}
	if(listGetSize(list)==0){
		return listInsertFirst(list,element);
	}
	Node tailNode = list->tail;
	Node lastNode = tailNode->previous;
	Node insertNode = createNode(list->tail,lastNode,list,element);
	if(!insertNode){
		return LIST_OUT_OF_MEMORY;
	}
	lastNode->next=insertNode;
	tailNode->previous = insertNode;
	list->listSize++;
	return LIST_SUCCESS;

}

ListResult listInsertBeforeCurrent(List list, ListElement element){
	if(!list){
		return LIST_NULL_ARGUMENT;
	}
	if(!getListCurrentAddress(list)){
		return LIST_INVALID_CURRENT;
	}
	Node beforeNode = getListCurrentAddress(list)->previous;
	if(beforeNode==NULL){
		return listInsertFirst(list,element);
	}
	Node nextNode = getListCurrentAddress(list);
	Node insertNode = createNode(nextNode,beforeNode,list,element);
	if(!insertNode){
		return LIST_OUT_OF_MEMORY;
	}
	beforeNode->next = insertNode;
	nextNode->previous = insertNode;
	list->listSize++;
	return LIST_SUCCESS;
}

ListResult listInsertAfterCurrent(List list, ListElement element){
	if(!list){
		return LIST_NULL_ARGUMENT;
	}
	if(!getListCurrentAddress(list)){
		return LIST_INVALID_CURRENT;
	}
	Node nextNode = getListCurrentAddress(list)->next;
	if(nextNode == list->tail){
		return listInsertLast(list,element);
	}
	Node beforeNode = getListCurrentAddress(list);
	Node insertNode = createNode(nextNode,beforeNode,list,element);
	if(!insertNode){
		return LIST_OUT_OF_MEMORY;
	}
	beforeNode->next = insertNode;
	nextNode->previous = insertNode;
	list->listSize++;
	return LIST_SUCCESS;
}

ListResult listRemoveCurrent(List list){
	if(!list){
		return LIST_NULL_ARGUMENT;
	}
	Node nodeToDestroy = getListCurrentAddress(list);
	if(!nodeToDestroy){
		return LIST_INVALID_CURRENT;
	}
	list->freeElement(nodeToDestroy->data);
	Node previousNode = nodeToDestroy->previous;
	Node nextNode = nodeToDestroy->next;
	if(previousNode){
		previousNode->next = nextNode;
	}
	if(nextNode){
		nextNode->previous = previousNode;
	}
	if(nodeToDestroy==getListHeadAddress(list)){
		list->head = nextNode;
	}
	free(nodeToDestroy);
	list->current = NULL;
	list->listSize--;
	return LIST_SUCCESS;
}

//help function, swap the point address of 2 given ListElement addresses.
static void swapElementAddress(Node first,Node second){
	if(!first || !second){
		return;
	}
	ListElement temp = first->data;
	first->data = second->data;
	second->data = temp;
	return;
}

ListResult listClear(List list){
	int i;
	if(!list){
		return LIST_NULL_ARGUMENT;
	}
	listGetFirst(list);
	Node nextNode = getNextNode(getListCurrentAddress(list));
	int listSize = listGetSize(list);
	for ( i = 0; i < listSize; ++i) {
		listRemoveCurrent(list);
		listGetNext(list);
		if(nextNode!=list->tail){
			setListCurrentAddress(list,nextNode);
			nextNode = getNextNode(nextNode);
		}
	}
	return LIST_SUCCESS;
}


void listDestroy(List list){
	if(!list){
		return;
	}
	listClear(list);
	free(list->tail);
	free(list);
}
//********************************************* dbl_List*****************************************//

list dbl_List;

int compare(int k, list_node node1){
	if(node1->key==0 && node1->val=='h') return 1;
	if(node1->key==0 && node1->val=='t') return -1;
	return (k - node1->key);
}

list_node nodeCreate(list_node p,list_node n,int k, char v){
	list_node result=(struct node_type*) malloc(sizeof(struct node_type));
	result->key=k;
	result->val=v;
	result->prev=p;
	result->next=n;
	lock_init(result->lock);
	return result;
}


//************************ functions for the Generic Zombies List****************************//
ListElement copyNode(ListElement n){
	return n;
}

void destroyNode(ListElement n){
	lock_destroy( ((list_node)(n))->lock);
	free(n);
}

//**********************************dbl_List Functins********************************************//

void Initialize(){
	dbl_List= (struct dbl_list*) malloc(sizeof(struct dbl_list));
	dbl_List->head  =  nodeCreate(NULL,dbl_List->tail,0,'h');
	dbl_List->tail  =  nodeCreate(dbl_List->head,NULL,0, 't');
	dbl_List->head->next =dbl_List->tail;
	dbl_List->zombies=listCreate(copyNode, destroyNode );
}

void Destroy(){
	list_node n=dbl_List->head->next;
	for(; n!=NULL ; n=n->next ){
		destroyNode(n->prev);
	}
	destroyNode(dbl_List->tail);
	listDestroy(dbl_List->zombies);
	free(dbl_List);
}

bool InsertHead(int key, char data){
	list_node new_node;
	int result1, result2;
	list_node n=dbl_List->head;
	get_may_write_lock(n->lock);

	while(n!=dbl_List->tail){
//		 if(n->key==0 && n->val=='d'){ // this node was deleted
//			 get_may_write_lock(n->prev->lock);
//			 release_shared_lock(n->lock);
//			 n=n->prev;
//			 continue;
//		 }
		 result1=compare(key, n);
		 result2=compare(key, n->next);
		 if(result1==0 || result2==0){
			 release_shared_lock(n->lock);
			 return false;
		 }
		 else if(result1>0 && result2>0 ){
			 get_may_write_lock(n->next->lock);
			 n=n->next;
			 release_shared_lock(n->prev->lock);
			 continue;
		 }
		 else if(result1>0 && result2<0){
			 upgrade_may_write_lock(n->lock);  // upgrade lock

			 new_node=nodeCreate(n, n->next,key, data);  // a new node is created
			 n->next->prev=new_node;
			 n->next=new_node;

			 release_exclusive_lock(n->lock);  // release write lock
			 return true;
		 }
		//TODO: remove before submition
		 printf(" \n error- illegal condition in insert head.");
		 assert(false);
	}
	release_shared_lock(n->lock);
	return false;
}

bool InsertTail(int key, char data){
	list_node new_node;
	int result1, result2;
	list_node n=dbl_List->tail->prev;
	get_may_write_lock(n->lock);
	while(n!=NULL){
		 if(n->key==0 && n->val=='d'){ // this node was deleted
				 get_may_write_lock(n->next->lock);
				 release_shared_lock(n->lock);
				 n=n->next;
				 continue;
			 }
		 result1=compare(key, n);
		 result2=compare(key, n->next);
		 if(result1==0 || result2==0){
		 			 release_shared_lock(n->lock);
		 			 return false;
		 		 }
		 else if(result1<0 && result2<0 ){
			   release_shared_lock(n->lock);
			   n=n->prev;
			  get_may_write_lock(n->lock);
			  continue;
			 }
		 else if(result1>0 && result2<0){
					 upgrade_may_write_lock(n->lock);  // upgrade lock

					 new_node=nodeCreate(n, n->next,key, data);  // a new node is created
					 n->next->prev=new_node;
					 n->next=new_node;

					 release_exclusive_lock(n->lock);  // release write lock
					 return true;
				 }
		 else if(result1>0 && result2>0){ // we passed
			 get_may_write_lock(n->next->lock);
			 n=n->next;
			 release_shared_lock(n->prev->lock);
		 }
			//TODO: remove before submition
			 printf(" \n error- illegal condition in insert tail.");
			 assert(false);
		 break;
	}
	//TODO: remove before submition
	 printf(" \n error- illegal condition in insert tail.");
	 assert(false);
	return false;
}

bool Delete(int key){
	int result;
	list_node temp;
		list_node n=dbl_List->head;
		get_may_write_lock(n->lock);
		get_may_write_lock(n->next->lock);

		while(n->next!=dbl_List->tail){
//			 if(n->key==0 && n->val=='d'){ // this node was deleted
//				 get_may_write_lock(n->prev->lock);
//				 release_shared_lock(n->lock);
//				 n=n->prev;
//				 continue;
//			 }
			 result=compare(key, n->next);
			 if(result==0){
				 upgrade_may_write_lock(n->lock);
				 upgrade_may_write_lock(n->next->lock);

				 n->next->key=0;  // mark as deleted
				 n->next->val='d';
				 temp=n->next;  // disconnect
				 n->next->next->prev=n;
				 n->next=n->next->next;
				 listInsertFirst(dbl_List->zombies, temp);  // add deleted node to zombie list


				 release_exclusive_lock(temp->lock);
				 release_exclusive_lock(n->lock);


				 return true;
			 }
			 else if(result>0){
				  get_may_write_lock(n->next->next->lock);
				   n=n->next;
				 release_shared_lock(n->prev->lock);
				 continue;
			 }
			 break;
		}
}

bool Search(int key, char* data){
	int result;
	list_node n=dbl_List->head;
	get_read_lock(n->lock);
	while(n!=dbl_List->tail){
//		 if(n->key==0 && n->val=='d'){ // this node was deleted
//			 get_read_lock(n->prev->lock);
//			 release_shared_lock(n->lock);
//			 n=n->prev;
//			 continue;
//		 }
		 result=compare(key, n);
		 if(result==0){
			 *data=n->val;
			 release_shared_lock(n->lock);
			 return true;
		 }
		 else if(result>0){
			 get_read_lock(n->next->lock);
			 n=n->next;
			 release_shared_lock(n->prev->lock);
			 continue;
		 }
		 break;
	}
	release_shared_lock(n->lock);
	return false;
}



